package puzzle.projecteuler.p200;



public class Problem112B {

	/**
	 * f(m), g(m)分别表示<=m的increasing\decreasing数的数目。
	 * bouncy(m) = m-f(m)-g(m)+c
	 * c是同属于increasing和decreasing数的数数，比如111, 99999
	 * 
	 * 这个问题的关键是建立合适的递推关系计算f(m)，请参考
	 * {@link #f(int, int[])}。
	 *  
	 * g(m)则直接利用了f的计算结果。
	 * 
	 * 注意一个细节，这里满足条件的数一定是100的倍数。
	 * 
	 * 实际上，本题通过Brue Force就可以解决，但是Problem113就不行了。
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		int m = 15872;
		for (int i = 1; i < m; i ++) {
			int n = i*100;
			if (bouncy(n) == i*99) {
				System.out.println(n);
				break;
			}
		}
	}

	private static int[] toArray(long m) {
		char[] cs = String.valueOf(m).toCharArray();
		int[] ms = new int[cs.length];
		for (int i = 0; i < ms.length; i ++) {
			ms[i] = cs[i]-'0';
		}
		return ms;
	}
	
	/**
	 * bouncy(m) = m-f(m)-g(m)+c
	 * @param m
	 * @return
	 */
	private static long bouncy(long m) {
		
		//get c
		int c = 0;
		String str_m = String.valueOf(m);
		char[] cs = str_m.toCharArray();
		int l = cs.length;
		c += 9*(l-1)+1;	//0,1,2,...,9,11,22,...,99,......,99..99(l-1个9)
		//
		for (int i = 1; i < 10; i ++) {
			String tmp = "";
			for (int j = 0; j < l; j ++) {
				tmp += i;
			}
			if (m >= Long.valueOf(tmp)) c++;
		}
		//return
		return (m+1)-f(m)-g(m)+c;
	}

	private static long f(long m) {
		
		return f(0, toArray(m));
	}
	
	private static long g(long m) {
		
		String str_m = String.valueOf(m);
		char[] cs = str_m.toCharArray();
		long count = 0;
		//part 1
		int[] tmp1 = null;
		for (int k = 1; k < cs.length; k ++) {
			if (k == 1) {
				count += 10;
			} else {
				tmp1 = new int[k];
				tmp1[0] = 8;
				for (int i = 1; i < tmp1.length; i ++) {
					tmp1[i] = 9;
				}
				count += f(0, tmp1);
			}
//			System.out.println(count);
		}
		
		//part 2
		long m1 = 0, m2 = 0;
		for (int i = 0; i < cs.length; i ++) {
			if (i == 0) {
				m1 = 8;
			} else {
				m1 *= 10;
				m1 += 9;
			}
			m2 *= 10;
			m2 += 9-(cs[i]-'0');
		}
		m2 -= 1;
//		System.out.println(m1+","+m2);
		count += (f(0, toArray(m1))-f(0, toArray(m2)));
		return count;
	}

	/**
	 * 满足下面条件的数的个数：
	 * 1）increasing数
	 * 2）每位都不小于a
	 * 3）数值不超过十进制数 (m_1m_2...m_n)
	 * @param a
	 * @param ms
	 * @return
	 */
	private static long f(int a, int[] ms) {

		if (ms.length == 0) {
			return 0;
		} else if (ms.length == 1) {
			if (ms[0] >= a) {
				return ms[0]-a+1;
			} else {
				return 0;
			}
		} else {
			if (ms[0] < a) {
				return 0;
			} else if (ms[0] == a) {
				int[] tmp = new int[ms.length-1];
				System.arraycopy(ms, 1, tmp, 0, tmp.length);
				return f(a, tmp);
			} else {
				long count = 0;
				int[] tmp = new int[ms.length-1];
				for (int i = 0; i < tmp.length; i ++) {
					tmp[i] = 9;
				}
				for (int m = a; m < ms[0]; m ++) {
					count += f(m, tmp);
				}
				System.arraycopy(ms, 1, tmp, 0, tmp.length);
				count += f(ms[0], tmp);
				return count;
			}
		}
	}
}
